

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @author HuRui
 * create on 2018/12/24 17:42
 */
public class Tree {
    /**
     * 所有节点
     */
    private List<TreeNode> allElement;
    /**
     * 默认元素个数
     */
    private int defaultCapacity = 120;
    /**
     * 已有元素
     */
    private int count;

    public Tree() {
        allElement = new ArrayList<>(defaultCapacity);
        count = 0;
    }

    public Tree(int capacity) {
        allElement = new ArrayList<>(capacity);
        count = 0;
    }

    public void setRoot(String root) {
        TreeNode rootNode = new TreeNode(root, -1, 1);
        allElement.clear();
        allElement.add(rootNode);
        count++;
    }

    public void add(String node) {
        String[] split = node.split("/");
        for (int i = 0; i < split.length; i++) {
            String s = split[i];
            if (count == 0) {
                setRoot(s);
                continue;
            }
            int index = index(new TreeNode(s, i + 1));
            if (index == -2) {
                int indexParent = index(new TreeNode(split[i - 1], i));
                TreeNode treeNode = new TreeNode(s, indexParent, i + 1);
                allElement.add(treeNode);
                count++;
            }
        }
    }

    private int index(TreeNode treeNode) {
        for (int i = 0; i < count; i++) {
            if (Objects.equals(allElement.get(i).getNode(), treeNode.getNode()) &&
                    allElement.get(i).getLevel() == treeNode.getLevel()) {
                return i;
            }
        }
        return -2;
    }

    private List<String> findAllChildren(TreeNode treeNode) {
        int index = index(treeNode);
        if (index == -2) {
            return null;
        }
        List<String> treeNodes = new ArrayList<>();
        for (TreeNode treeNode1 : allElement) {
            if (treeNode1.getParent() == index && treeNode1.getLevel() == treeNode.getLevel() + 1) {
                treeNodes.add(treeNode1.getNode());
            }
        }
        return treeNodes;
    }

    public boolean search(String url) {
        if (url == null) {
            return false;
        }
        String[] split = url.split("/");
        int length = split.length;
        for (int i = 0; i < length - 1; i++) {
            List<String> allChildren = findAllChildren(new TreeNode(split[i], i + 1));
            if (!allChildren.contains(split[i + 1])) {
                return false;
            }
        }
        return true;
    }

    private void printTree() {
        for (int i = 1; i < 10; i++) {
            for (TreeNode treeNode : allElement) {
                if (treeNode.level == i) {
                    System.out.print(treeNode.getNode());
                    System.out.print("\t\t");
                }
            }
            System.out.println();
        }
    }


    private static class TreeNode {
        /**
         * 节点值
         */
        private String node;
        /**
         * 父节点位置
         */
        private int parent;
        /**
         * 所在层级
         */
        private int level;

        public TreeNode(String node, int parent, int level) {
            this.node = node;
            this.parent = parent;
            this.level = level;
        }

        private TreeNode(String node, int level) {
            this.node = node;
            this.level = level;
        }

        public String getNode() {
            return node;
        }

        public void setNode(String node) {
            this.node = node;
        }

        public int getParent() {
            return parent;
        }

        public void setParent(int parent) {
            this.parent = parent;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }
    }

    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.add("api/user/auth/chat/find/findAll");
        tree.add("api/test/auth/te/find/tee");
//        tree.add("api/s/auth/te/find/tede");
//        tree.add("api/tdest/d/te/fidnd/tee");
//        tree.add("api/tedst/autdh/te/fidnd/tee");
//        tree.add("api/tedst/autdh/te/fidnd/tee");
//        tree.add("api/tedstd/autdhd/te/fidnd/tee");
//        tree.add("api/tedst/autdhd/te/fidnd/tee");
//        tree.add("api/tedsdt/autdh/tde/fidnd/tee");
        boolean search = tree.search("api/test/auth/te/find/tee");
        System.out.println(search);
    }
}

